//leetcode 494 目标和
public class Test3 {
    int ret;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return ret;
    }

    private void dfs(int[] nums, int target, int pos, int sum) {
        if (pos == nums.length) {
            if (sum == target) ret++;
            return;
        }

        dfs(nums, target, pos + 1, sum + nums[pos]);
        dfs(nums, target, pos + 1, sum - nums[pos]);
    }
}
